home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / misc / amicvs1-0.lha / AmiCVS / scr / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-04-01  |  6.2 KB  |  339 lines
  1. /*
  2.  * Copyright (c) 1992, Brian Berliner and Jeff Polk
  3.  * 
  4.  * You may distribute under the terms of the GNU General Public License as
  5.  * specified in the README file that comes with the CVS 1.3 kit.
  6.  * 
  7.  * Polk's hash list manager.  So cool.
  8.  */
  9.  
  10. #include "cvs.h"
  11.  
  12. #ifndef lint
  13. static char rcsid[] = "@(#)hash.c 1.14 92/03/31";
  14. #endif
  15.  
  16. /* global caches */
  17. static List *listcache = NULL;
  18. static Node *nodecache = NULL;
  19.  
  20. #if __STDC__
  21. static void freenode_mem (Node * p);
  22. #else
  23. static void freenode_mem ();
  24. #endif                /* __STDC__ */
  25.  
  26. /* hash function */
  27. static int
  28. hashp (key)
  29.     char *key;
  30. {
  31.     register char *p;
  32.     register int n = 0;
  33.  
  34.     for (p = key; *p; p++)
  35.     n += *p;
  36.  
  37.     return (n % HASHSIZE);
  38. }
  39.  
  40. /*
  41.  * create a new list (or get an old one from the cache)
  42.  */
  43. List *
  44. getlist ()
  45. {
  46.     int i;
  47.     List *list;
  48.     Node *node;
  49.  
  50.     if (listcache != NULL)
  51.     {
  52.     /* get a list from the cache and clear it */
  53.     list = listcache;
  54.     listcache = listcache->next;
  55.     list->next = (List *) NULL;
  56.     for (i = 0; i < HASHSIZE; i++)
  57.         list->hasharray[i] = (Node *) NULL;
  58.     }
  59.     else
  60.     {
  61.     /* make a new list from scratch */
  62.     list = (List *) xmalloc (sizeof (List));
  63.     bzero ((char *) list, sizeof (List));
  64.     node = getnode ();
  65.     list->list = node;
  66.     node->type = HEADER;
  67.     node->next = node->prev = node;
  68.     }
  69.     return (list);
  70. }
  71.  
  72. /*
  73.  * free up a list
  74.  */
  75. void
  76. dellist (listp)
  77.     List **listp;
  78. {
  79.     int i;
  80.     Node *p;
  81.  
  82.     if (*listp == (List *) NULL)
  83.     return;
  84.  
  85.     p = (*listp)->list;
  86.  
  87.     /* free each node in the list (except header) */
  88.     while (p->next != p)
  89.     delnode (p->next);
  90.  
  91.     /* free any list-private data, without freeing the actual header */
  92.     freenode_mem (p);
  93.  
  94.     /* free up the header nodes for hash lists (if any) */
  95.     for (i = 0; i < HASHSIZE; i++)
  96.     {
  97.     if ((p = (*listp)->hasharray[i]) != (Node *) NULL)
  98.     {
  99.         /* put the nodes into the cache */
  100.         p->type = UNKNOWN;
  101.         p->next = nodecache;
  102.         nodecache = p;
  103.     }
  104.     }
  105.  
  106.     /* put it on the cache */
  107.     (*listp)->next = listcache;
  108.     listcache = *listp;
  109.     *listp = (List *) NULL;
  110. }
  111.  
  112. /*
  113.  * get a new list node
  114.  */
  115. Node *
  116. getnode ()
  117. {
  118.     Node *p;
  119.  
  120.     if (nodecache != (Node *) NULL)
  121.     {
  122.     /* get one from the cache */
  123.     p = nodecache;
  124.     nodecache = p->next;
  125.     }
  126.     else
  127.     {
  128.     /* make a new one */
  129.     p = (Node *) xmalloc (sizeof (Node));
  130.     }
  131.  
  132.     /* always make it clean */
  133.     bzero ((char *) p, sizeof (Node));
  134.     p->type = UNKNOWN;
  135.  
  136.     return (p);
  137. }
  138.  
  139. /*
  140.  * remove a node from it's list (maybe hash list too) and free it
  141.  */
  142. void
  143. delnode (p)
  144.     Node *p;
  145. {
  146.     if (p == (Node *) NULL)
  147.     return;
  148.  
  149.     /* take it out of the list */
  150.     p->next->prev = p->prev;
  151.     p->prev->next = p->next;
  152.  
  153.     /* if it was hashed, remove it from there too */
  154.     if (p->hashnext != (Node *) NULL)
  155.     {
  156.     p->hashnext->hashprev = p->hashprev;
  157.     p->hashprev->hashnext = p->hashnext;
  158.     }
  159.  
  160.     /* free up the storage */
  161.     freenode (p);
  162. }
  163.  
  164. /*
  165.  * free up the storage associated with a node
  166.  */
  167. static void
  168. freenode_mem (p)
  169.     Node *p;
  170. {
  171.     if (p->delproc != (void (*) ()) NULL)
  172.     p->delproc (p);            /* call the specified delproc */
  173.     else
  174.     {
  175.     if (p->data != NULL)        /* otherwise free() it if necessary */
  176.         free (p->data);
  177.     }
  178.     if (p->key != NULL)            /* free the key if necessary */
  179.     free (p->key);
  180.  
  181.     /* to be safe, re-initialize these */
  182.     p->key = p->data = (char *) NULL;
  183.     p->delproc = (void (*) ()) NULL;
  184. }
  185.  
  186. /*
  187.  * free up the storage associated with a node and recycle it
  188.  */
  189. void
  190. freenode (p)
  191.     Node *p;
  192. {
  193.     /* first free the memory */
  194.     freenode_mem (p);
  195.  
  196.     /* then put it in the cache */
  197.     p->type = UNKNOWN;
  198.     p->next = nodecache;
  199.     nodecache = p;
  200. }
  201.  
  202. /*
  203.  * insert item p at end of list "list" (maybe hash it too) if hashing and it
  204.  * already exists, return -1 and don't actually put it in the list
  205.  * 
  206.  * return 0 on success
  207.  */
  208. int
  209. addnode (list, p)
  210.     List *list;
  211.     Node *p;
  212. {
  213.     int hashval;
  214.     Node *q;
  215.  
  216.     if (p->key != NULL)            /* hash it too? */
  217.     {
  218.     hashval = hashp (p->key);
  219.     if (list->hasharray[hashval] == NULL)    /* make a header for list? */
  220.     {
  221.         q = getnode ();
  222.         q->type = HEADER;
  223.         list->hasharray[hashval] = q->hashnext = q->hashprev = q;
  224.     }
  225.  
  226.     /* put it into the hash list if it's not already there */
  227.     for (q = list->hasharray[hashval]->hashnext;
  228.          q != list->hasharray[hashval]; q = q->hashnext)
  229.     {
  230.         if (strcmp (p->key, q->key) == 0)
  231.         return (-1);
  232.     }
  233.     q = list->hasharray[hashval];
  234.     p->hashprev = q->hashprev;
  235.     p->hashnext = q;
  236.     p->hashprev->hashnext = p;
  237.     q->hashprev = p;
  238.     }
  239.  
  240.     /* put it into the regular list */
  241.     p->prev = list->list->prev;
  242.     p->next = list->list;
  243.     list->list->prev->next = p;
  244.     list->list->prev = p;
  245.  
  246.     return (0);
  247. }
  248.  
  249. /*
  250.  * look up an entry in hash list table
  251.  */
  252. Node *
  253. findnode (list, key)
  254.     List *list;
  255.     char *key;
  256. {
  257.     Node *head, *p;
  258.  
  259.     if (list == (List *) NULL)
  260.     return ((Node *) NULL);
  261.  
  262.     head = list->hasharray[hashp (key)];
  263.     if (head == (Node *) NULL)
  264.     return ((Node *) NULL);
  265.  
  266.     for (p = head->hashnext; p != head; p = p->hashnext)
  267.     if (strcmp (p->key, key) == 0)
  268.         return (p);
  269.     return ((Node *) NULL);
  270. }
  271.  
  272. /*
  273.  * walk a list with a specific proc
  274.  */
  275. int
  276. walklist (list, proc)
  277.     List *list;
  278.     int (*proc) ();
  279. {
  280.     Node *head, *p;
  281.     int err = 0;
  282.  
  283.     if (list == NULL)
  284.     return (0);
  285.  
  286.     head = list->list;
  287.     for (p = head->next; p != head; p = p->next)
  288.     err += proc (p);
  289.     return (err);
  290. }
  291.  
  292. /*
  293.  * sort the elements of a list (in place)
  294.  */
  295. void
  296. sortlist (list, comp)
  297.     List *list;
  298.     int (*comp) ();
  299. {
  300.     Node *head, *remain, *p, *q;
  301.  
  302.     /* save the old first element of the list */
  303.     head = list->list;
  304.     remain = head->next;
  305.  
  306.     /* make the header node into a null list of it's own */
  307.     head->next = head->prev = head;
  308.  
  309.     /* while there are nodes remaining, do insert sort */
  310.     while (remain != head)
  311.     {
  312.     /* take one from the list */
  313.     p = remain;
  314.     remain = remain->next;
  315.  
  316.     /* traverse the sorted list looking for the place to insert it */
  317.     for (q = head->next; q != head; q = q->next)
  318.     {
  319.         if (comp (p, q) < 0)
  320.         {
  321.         /* p comes before q */
  322.         p->next = q;
  323.         p->prev = q->prev;
  324.         p->prev->next = p;
  325.         q->prev = p;
  326.         break;
  327.         }
  328.     }
  329.     if (q == head)
  330.     {
  331.         /* it belongs at the end of the list */
  332.         p->next = head;
  333.         p->prev = head->prev;
  334.         p->prev->next = p;
  335.         head->prev = p;
  336.     }
  337.     }
  338. }
  339.